package main.java.LeetCode.ClassicalAlgorithm.KnapsackProblem.Impl;

import main.java.LeetCode.ClassicalAlgorithm.KnapsackProblem.Knapsack;

/**
 * 完全背包
 */
public class UnboundedKnapsack implements Knapsack {
    @Override
    public int bestChoose(int[] weights, int[] values, int cap) {
        assert weights.length==values.length;

        int[] dp = new int[cap+1];
        for(int i = 0;i<weights.length;i++){
            int weight = weights[i];
            int value = values[i];

            for(int j = weight;j<=cap;j++){
                dp[j] = Math.max(dp[j],dp[j-weight]+value);
            }
        }
        return dp[cap];
    }

    @Override
    public int bestChooseForMultiple(int[] conditions1, int[] conditions2, int[] values, int cap1, int cap2) {
        throw new RuntimeException("该方法只使用与多条件的背包");
    }
}
